"""
    6. 0-1 背包问题
    有n个商品，第i个商品价值vi 元， 中 wi 千克， 拿走价值尽量搞，但背包最多容纳 w 千克的东西。

    0-1 背包：
        对于商品，要不全拿，要不不拿。
    
    商品1 v = 60 w = 10
    商品2 v = 100 w = 20
    商品3 v = 120 w = 30
    背包容量 w = 50
    1. 背包容量不够

    ​	value_max = `v[k-1][w]`  # 就是在 0----k-1 件中， 且背包容量为 w的最大价值

	2. 背包容量够

    	1. 不取

        ​	value_max1 = `v[k-1][w]`  # 就是在 0----k-1 件中， 且背包容量为 w的最大价值

    	2. 取

        ​	value_max2 = `v[k-1][w-kw] + Vw`   # 要查看 在 背包容量为 w - kw 的情况下 0 到 k-1件商品中最高价值 加上 当前商品的价值。 因为 要腾出容量存当前物体

        ​	例如： 看容量20时，取第五件的价值需要：(5件商品 体积7 价值10)

        ​				容量为 20 -1 = 13 时： 0-4 的最高价值 即  `B[4][13]+ 10`  

    最终决定取不取就是 max(value_max1，value_max2 ) 看哪个大。

"""
import pprint

W = [0, 2, 3, 4, 5, 9] # 物品重量
V = [0, 3, 4, 5, 8, 10]    # 物品价值


def get_max(cap):
    B = [[0 for i in range(cap+1)] for i in range(len(W))]
    for k in range(0, len(W)):  # 物品个数
        for w in range(0, cap+1): # 背包容量
            if W[k] > w: # 如果第n 个的体积大于背包容量
                B[k][w] = B[k-1][w]  # 0-k 里最大价值就是 在背包容量为 w时 0 到 k-1 件商品内的最大价值
            else:  # B[k-1][w-W[k]] + V[k] 查看 在 背包容量为 w - kw 的情况下 0 到 k-1件商品中最高价值 加上 当前商品的价值。 因为 要腾出容量存当前物体
                B[k][w] = max(B[k-1][w-W[k]] + V[k],   B[k-1][w])  # 应该时取和不取两种情况下的最大值
    return B[len(W)-1][cap], B
                
result, B = get_max(20)
pprint.pprint(B)

# 假如说我要知道有哪些物品, 如果  B[k][cap] == B[k-1][cap-W[k]] + V[k] 说明这件物品找到了， 接下来就应该看，容量为 cap-W[k] 背包的选物情况了。
def get_items(cap, B):
    for k in range(len(W)-1, 0, -1):
        while cap > 0:
            if B[k][cap] == B[k-1][cap-W[k]] + V[k]:
                # 说明第k件取到了
                print(k)
                cap = cap-W[k]
            break
        
get_items(20, B)

            
            
    